package greedy_algorithm

import "sort"

type Item struct {
	Wgt int
	Val int
}

func FractionalKnapsack(wgt []int, val []int, cap int) float64 {
	items := make([]*Item, len(wgt))
	for i, v := range wgt {
		items[i] = &Item{
			Wgt: v,
			Val: val[i],
		}
	}
	sort.Slice(items, func(i, j int) bool {
		return float64(items[i].Val)/float64(items[i].Wgt) > float64(items[j].Val)/float64(items[j].Wgt)
	})

	result := float64(0)

	for _, it := range items {
		if it.Val < cap {
			result += float64(it.Val)
			cap -= it.Wgt
		} else {
			// 装一部分进去
			result += float64(it.Val) / float64(it.Wgt) * float64(cap)
			break
		}
	}
	return result
}
